//! ## 21. Merge Two Sorted Lists (easy, recursion, singly_list)
//! Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
//!
//! #### Example 1
//! ```txt
//! Input: l1 = [1,2,4], l2 = [1,3,4]
//! Output: [1,1,2,3,4,4]
//! ```
//! #### Example 2
//! ```txt
//! Input: l1 = [], l2 = []
//! Output: []
//! ```
//! #### Example 3
//! ```txt
//! Input: l1 = [], l2 = [0]
//! Output: [0]
//! ```
//! #### Constraints
//! - The number of nodes in both lists is in the range `[0, 50]`.
//! - `-100 <= Node.val <= 100`
//! - Both l1 and l2 are sorted in **non-decreasing** order.
//!
//! ### 知识点
//! - 递归
//!

pub struct Solution;
use myutils::list::singly_list::SinglyList;

impl Solution {
    /// #### 原理
    /// 使用递归的方式合并两个单链表
    /// #### 流程
    /// 判断 l1 l2 第一个元素的大小, 如果 l1 < l2 则 l1.next = 递归合并 l1.next 和 l2, 返回 l1; 否则, l2.next = 递归合并 l2.next 和 l1, 返回 l2.
    ///
    /// 递归结束条件: l1 空时返回 l2; l2 空时返回 l1;
    /// #### 边界分析
    /// l1, l2 为空的边界已覆盖.
    /// #### 复杂度
    /// - 时间复杂度
    ///     - O(n+m), 其中 n 和 m 分别为两个链表的长度. 因为每次调用递归都会去掉 l1 或者 l2 的头节点(直到至少有一个链表为空), 函数 solve 至多只会递归调用每个节点一次. 因此, 时间复杂度取决于合并后的链表长度, 即 O(n+m).
    /// - 空间复杂度
    ///     - O(n+m), 递归调用需要消耗栈空间, 其空间复杂度取决于递归深度, 本题递归调用最多 n + m 次.
    pub fn solve(l1: SinglyList<i32>, l2: SinglyList<i32>) -> SinglyList<i32> {
        if l1.is_none() {
            return l2;
        }
        if l2.is_none() {
            return l1;
        }

        let mut l1 = l1.unwrap();
        let mut l2 = l2.unwrap();
        if l1.val < l2.val {
            l1.next = Self::solve(l1.next, Some(l2));
            Some(l1)
        } else {
            l2.next = Self::solve(l2.next, Some(l1));
            Some(l2)
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    // singly_list! 的依赖要导入进来
    use myutils::list::singly_list::ListMaker;
    use myutils::singly_list;

    #[test]
    fn test() {
        let a = singly_list!(1, 2, 4);
        let b = singly_list!(1, 3, 4);
        let c = singly_list!(1, 1, 2, 3, 4, 4);
        assert_eq!(Solution::solve(a, b), c);
    }
}
